Основы кибернетики

1. Что такое кибернетика и какова ее история развития? Какие основные разделы кибернетики вы знаете? В чем заключается принцип обратной связи в кибернетике?

Кибернетика — наука об общих закономерностях получения, хранения, преобразования и передачи информации в сложных управляющих системах, будь то машины, живые организмы или общество. История кибернетики началась в середине 20 века. В 1948 г появилась книга "Кибернетика, или управление и связь в животном и машине". Она положила начало формированию кибернетики как самостоятельной научной области.
Основные разделы кибернетики включают:

• теория информации
• теория алгоритмов
• теория автоматов
• исследование операций
• теория оптимального управления
• теория распознавания образов

Принцип обратной связи в кибернетике заключается в том, что информация о воздействии системы на окружающую среду возвращается обратно к этой системе, позволяя ей анализировать и корректировать свое поведение в соответствии с полученными данными. Такая обратная связь позволяет системе быть гибкой и гарантировать ее адаптацию к изменяющимся условиям и требованиям.

2. Что такое информация и какие существуют подходы к ее измерению? Как связаны понятия энтропии и информации в кибернетике?

Информация — это то, что помогает нам разобраться в неизвестном или неопределенном. В кибернетике и теории информации, информация представляет собой средство избавления от неопределенности.

Подходы к измерению информации:

• Содержательный подход (с точки зрения человека: полезность, срочность информации)
• Алфавитный подход (с точки зрения технических устройств: кол-во символов в алфавите и в сообщении)
• Вероятностный подход (чем меньше вероятность возникновения события, тем больше информации содержится в этом событии)

Связь энтропии и информации в кибернетике.
Информация и энтропия связаны, потому что они характеризуют реальную действительность с точки зрения упорядоченности и хаоса, причем если информация – мера упорядоченности, то энтропия – мера беспорядка. Информация и энтропия в сумме дают всё состояние системы, событие с большим количеством информации уменьшает энтропию и наоборот.

3. Приведите примеры реализации кибернетических систем и их применения в различных сферах деятельности. Какие перспективы развития кибернетики можно выделить и какие новые направления и задачи могут возникнуть в будущем?

Примеры реализации кибернетических систем и их применение:

• Автопилоты в авиации:
  Системы автопилота в самолетах используют обратные связи и датчики для автоматического управления полетом, повышая точность и безопасность.
• Промышленные роботы:
  Кибернетические системы в производстве, например, роботы на заводах, автоматизируют процессы сборки, упаковки и манипуляции.
• Интеллектуальные системы управления в транспорте:
  Системы управления транспортом, основанные на искусственном интеллекте, оптимизируют движение транспорта, улучшая эффективность и снижая пробки.
• Медицинская диагностика с использованием ИИ:
  Кибернетические системы в медицине, например, с использованием искусственного интеллекта для анализа медицинских изображений, помогают в диагностике заболеваний.

Перспективы и будущие направления в кибернетике:

• Развитие искусственного интеллекта:
  Улучшение алгоритмов машинного обучения и разработка более сложных и интеллектуальных систем.
• Киберфизические системы для умных городов:
  Использование киберфизических систем для управления инфраструктурой, энергосистемами и транспортом в городах.
• Робототехника и автономные системы:
  Развитие более гибких, маневренных роботов и систем для автономного функционирования в различных средах.
• Кибербезопасность:
  Борьба с угрозами кибербезопасности и разработка более совершенных методов защиты информации.
• Биокибернетика и интерфейсы мозг-компьютер:
  Исследование взаимодействия между биологическими системами и компьютерами, создание улучшенных интерфейсов мозг-компьютер.

4. Что такое кибернетика, и какие разделы она включает? Каковы основные цели и задачи каждого раздела кибернетики? Как связаны между собой различные разделы кибернетики?

Кибернетика - наука об общих закономерностях получения, хранения, преобразования и передачи информации в сложных управляющих системах, будь то машины, живые организмы или общество. Она помогает понять, как работают разные вещи и использовать этот опыт для создания эффективных систем.

Основные цели и задачи разделов кибернетики:

• теория информации: изучает количественные закономерности, связанные с хранением, передачей и обработкой информации.
• теория алгоритмов: изучает общие свойства и закономерности алгоритмов, разнообразные формальные модели их представления.
• теория автоматов: изучает абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
• исследование операций: занимается разработкой и применением методов нахождения оптимальных решений.
• теория оптимального управления: занимается поиском управления динамической системой в течение определенного периода времени таким образом, чтобы целевая функция была оптимизирована.
• теория распознавания образов: развивает основы и методы классификации и идентификации предметов и явлений, которые характеризуются конечным набором некоторых свойств и признаков.

Связь между различными разделами кибернетики. Общие принципы управления, теории информации и обратной связи объединяют разделы, позволяя им взаимодействовать и взаимно обогащаться. Например, принципы обратной связи и математические методы исследования систем широко применяются во всех разделах кибернетики.

5. В чем заключается роль информации в кибернетической системе? Какие существуют меры информации, и как они используются в кибернетике? Поясните, что такое энтропия и как она связана с информацией.

Роль информации в кибернетической системе. Информация в кибернетике рассматривается как основная составляющая любой системы. Она описывает состояние системы и передается через различные каналы коммуникации. Кибернетика также изучает процессы передачи информации, ее обработку и использование в управлении системами.

Меры информации в кибернетике (?)

• Бит: Самая маленькая единица информации, принимающая значения 0 или 1.
• Байт: Группа из 8 бит, представляющая символ или число.
• Килобайт, мегабайт, гигабайт и т.д.: Большие единицы, измеряющие объем данных

Связь энтропии и информации в кибернетике
Информация и энтропия связаны, потому что они характеризуют реальную действительность с точки зрения упорядоченности и хаоса, причем если информация – мера упорядоченности, то энтропия – мера беспорядка. Информация и энтропия в сумме дают всё состояние системы, событие с большим количеством информации уменьшает энтропию и наоборот.

Системы счисления

1. Дайте определение системе счисления. Что такое основание системы счисления? Что такое разряд позиционной системы счисления? Перечислите известные вам системы счисления и укажите их основания. Опишите принцип работы непозиционной системы счисления. Опишите принцип работы позиционной системы счисления.

Система счисления — это метод представления чисел с использованием символов (цифр) и правил для их комбинирования.
Основание системы счисления — это количество уникальных цифр, используемых в системе. Например, в десятичной системе основание - 10, потому что используются цифры от 0 до 9.
Разряд позиционной системы счисления — это позиция цифры в числе, которая определяет её вес. Например, в числе 326, 3 - сотни, 2 - десятки, 6 - единицы.
Некоторые системы счисления и их основания:

• Десятичная (основание 10): 0, 1, 2, ..., 9.
• Двоичная (основание 2): 0, 1.
• Восьмеричная (основание 8): 0, 1, 2, ..., 7.
• Шестнадцатеричная (основание 16): 0, 1, 2, ..., 9, A, B, ..., F (где A-F представляют 10-15).

Принцип работы непозиционной системы счисления: Каждая цифра имеет фиксированный вес, независимо от своей позиции. Например, римская.
Принцип работы позиционной системы счисления: Значение цифры зависит от её места в числе. Мы умножаем каждую цифру на определенную степень основания и складываем результаты, чтобы получить общее значение числа.

2. Приведите пример перевода числа из одной системы счисления в другую. В чем разница между двоичной, десятичной и шестнадцатеричной системами счисления? В чем преимущество использования шестнадцатеричной системы счисления при работе с двоичными данными? В чем особенность двоичной системы счисления и почему она часто используется в компьютерной технике?

Пример перевода числа: Допустим, у нас есть число в десятичной системе - 27. Чтобы перевести его в двоичную систему, мы делим 27 на 2 и записываем остатки в обратном порядке. 27 в двоичной системе будет 11011.

Разница между системами счисления:

• Двоичная (основание 2): использует только две цифры (0 и 1).
• Десятичная (основание 10): использует десять цифр (0-9).
• Шестнадцатеричная (основание 16): использует шестнадцать цифр (0-9 и A-F, где A-F представляют 10-15).

Преимущество шестнадцатеричной системы: Каждые четыре символа двоичной системы можно перевести в один символ шестнадцатеричной системы. Шестнадцатеричная система помогает представлять большие двоичные данные компактно. Это удобно в программировании и компьютерах, где она упрощает визуальный анализ и редактирование данных.

Особенность двоичной системы: Компьютеры используют двоичную систему, потому что электронные устройства легче работают с двумя стабильными состояниями (0 и 1). Это делает обработку информации в компьютерах более эффективной.

3. Как выполняется сложение и вычитание чисел в двоичной системе счисления с использованием логических вентилей? Как выполняется умножение и деление чисел? Приведите пример использования систем счисления в вычислительной технике.

Сложение в двоичной системе с использованием логических вентилей:
Сложение в двоичной системе выполняется поразрядно. Полусумматор: исключающее ИЛИ используется для получения суммы, И – для переноса. Далее из двух полусумматоров и элемента ИЛИ составляют однобитный сумматор. Соединение однобитных сумматоров позволяет складывать числа различной величины.

Вычитание в двоичной системе с использованием логических вентилей:
Для вычитания в двоичной системе используют запись отрицательного числа в дополнительном коде, что позволяет заменить операцию вычитания на операцию сложения.

Умножение в двоичной системе:
Умножение в двоичной системе реализуется с помощью однобитных сумматоров и вентилей И. Умножение происходит аналогично умножению в столбик в десятичной системе, где элемент И используется для умножения однобитных чисел.

Деление в двоичной системе:
Для реализации деления на 2 может быть использован битовый сдвиг числа. Применение логических вентилей для автоматизации деления встречается реже из-за сложности операции.

Пример использования в вычислительной технике:
В компьютерах числа представлены и обрабатываются в двоичной системе, что делает электронные вычисления более эффективными. В арифметическо-логических блоках и регистрах процессора, таких как ALU, используется двоичная система счисления для операций.

4. Что такое логический сдвиг, арифметический сдвиг и циклический сдвиг? В чем между ними разница. Приведите примеры этих сдвигов? Каков арифметический смысл сдвигов?

*арифметический сдвиг влево = логический сдвиг влево

Логический сдвиг: перемещает биты без учета знака. (на пустое место подставляется 0)
Пример влево: 00101010 становится 01010100.

Арифметический сдвиг: сохраняет знак числа при сдвиге вправо. (первая цифра не меняется)
Пример вправо: 11011010 (отрицательное) становится 11110110.

Циклический сдвиг: выталкиваемые биты появляются с противоположной стороны.
Пример влево: 10100100 становится 01001001.

Арифметический смысл сдвигов: Арифметические сдвиги эквивалентны делению и умножению на степени двойки, что полезно в компьютерных операциях. Например: арифметический сдвиг вправо на один бит соответствует делению на 2, а арифметический сдвиг влево на один бит - умножению на 2.

5. Опишите принцип перевода целого и дробного числа из двоичной системы счисления в другие. Опишите принцип перевода целого и дробного числа десятичной системы счисления в двоичную.

Перевод целого числа из двоичной системы в десятичную.
Умножаем каждую цифру на 2 в степени, соответствующей её позиции, и складываем результаты.

Перевод целого числа из десятичной в двоичную.
Делаем деление на 2 с записью остатков, затем читаем остатки в обратном порядке.

Перевод дробного числа из двоичной системы в десятичную.
Аналогично целому числу, только умножаем каждую цифру после десятичной точки на степени 2 с отрицательными показателями.

Из десятичной в двоичную. Переводим целую и дробную части отдельно, для перевода дробной части умножаем её на 2 и записываем целую часть произведения (0 или 1), затем повторяем тоже самое для дробной части получившегося произведения.

0,0011

6. Перечислите степени двойки до 10ой степени. Опишите быстрый способ перевода числа из двоичной системы счисления в десятичную, в шестнадцатеричную.

Степени двойки:
2⁰=1
2¹=2
2²=4
2³=8
2⁴=16
2⁵=32
2⁶=64
2⁷=128
2⁸=256
2⁹=512
2¹⁰=1024

Быстрый способ перевода из двоичной в десятичную:
Сложить двойки в степенях позиций, на которых стоит 1 в двоичной системе.
3 2 1 0
1101₂=2³+2²+2⁰=8+4+1=13

Быстрый перевод из двоичной в шестнадцатеричную:
Поделить число в двоичной системе по четыре цифры, начиная справа, каждую четвёрку перевести в одну цифру шестнадцатеричной системы.
101101₂ -> 0010 1101 -> 2D₁₆

Логика

1. Теория множеств: основные определения и логические операции над множествами. Что такое диаграмма Эйлера? Как обозначаются основные логические операции с помощью диаграммы Эйлера?

Основные определения в теории множеств:

• Множество: Совокупность каких-либо элементов.
• Элемент множества: Одна из составляющих множества входящих в него величин.
• Пустое множество: Множество, не содержащее элементов.
• Мощность множества: Количество элементов в множестве.
• Универсальное множество: множество содержащие все возможные элементы.

Логические операции над множествами:

Диаграмма Эйлера — графическое представление множеств и их отношений с использованием окружностей, пересекающихся или не пересекающихся.

Обозначение логических операций с помощью диаграммы Эйлера

2. Что такое булевы функции? Что такое таблицы истинности? Взаимосвязь между булевой функцией и таблицей истинности. Как составить таблицу истинности для формулы логики? Как рассчитать количество строк в таблице истинности для заданной формулы логики?

Булевая функция — это функция, которая принимает булевы значения (истина или ложь) в качестве входных данных и возвращает булевое значение в качестве результата. Она описывается с использованием логических операций, таких как И, ИЛИ, НЕ, и других.

Таблицы истинности — это таблицы, отображающие все входные комбинации и результаты булевых функций.

Взаимосвязь между булевой функцией и таблицей истинности: Каждая строка в таблице истинности представляет комбинацию входов и результат соответствующей булевой функции.

Составление таблицы истинности:

• Определите переменные.
• Рассмотрите все комбинации булевых значений переменных.
• Примените булеву функцию для каждой комбинации.

Расчет количества строк в таблице истинности: Если есть n переменных, каждая из которых может принимать два значения (истина или ложь), то общее количество строк в таблице истинности будет 2ⁿ.

3. Булева алгебра: основные определения. Операция конъюнкции и дизъюнкции, их свойства. Операция отрицания, импликации и эквивалентности, их свойства. Представление булевых функций в виде логических выражений и таблиц истинности.

4. Что такое минимизация логических функций? Минимизация булевых функций с использованием карт Карно. Что такое ДНФ (дизъюнктивная нормальная форма)? Что такое КНФ (конъюнктивная нормальная форма)?

Минимизация логических функций — процесс упрощения булевых выражений для более эффективной работы в цифровых системах.

Минимизация булевых функций с использованием карт Карно:
Карты Карно — графический способ представления булевых функций с целью их удобной и наглядной ручной минимизации.

ДНФ (дизъюнктивная нормальная форма) — представление булевой функции в виде суммы произведений литералов (дизъюнкция простых конъюнкций).

КНФ (конъюнктивная нормальная форма) — представление булевой функции в виде произведения сумм литералов (конъюнкция простых дизъюнкций).

5. Применение булевой алгебры для проектирования цифровых схем. Использование булевых функций для представления переключательных функций. Что такое логический вентиль? Какие логические вентили вы знаете и как они работают? Нарисуйте обозначения основных логических вентилей и их таблицу истинности. Что такое цифровая логическая схема?

Применение булевой алгебры в цифровых схемах
В булевой алгебре переменные принимают два значения, так и в цифровых схемах существует два состояния: высокое напряжение и низкое напряжение. Это позволяет реализовывать логические функции в цифровых схемах.

Использование булевых функций для переключательных функций: (?)
Булевы функции представляют логические условия в цифровых схемах.

Логический вентиль — устройство, выполняющее логическую операцию в соответствии с булевой алгеброй.

(можно добавить элементы НЕ-И и НЕ-ИЛИ)

Цифровая логическая схема — комбинация логических вентилей для выполнения определенной функции в цифровой форме (например, сумматор, дешифратор или мультиплексор).

6. Что такое СДНФ (совершенная дизъюнктивная нормальная форма) и когда она используется? Что такое СКНФ (совершенная конъюнктивная нормальная форма) и когда она используется? В чем отличие СКНФ от КНФ, а СДНФ от ДНФ? В каких случаях используются СДНФ и СКНФ?

СДНФ (совершенная дизъюнктивная нормальная форма) — частный случай ДНФ, удовлетворяющий следующим трём условиям:

• в ней нет одинаковых слагаемых
• в каждом слагаемом нет повторяющихся переменных
• каждое слагаемое содержит все переменные, от которых зависит булева функция

(в таблице истинности берутся строки, где функция равна 1)

СКНФ (совершенная конъюнктивная нормальная форма) — частный случай КНФ, удовлетворяющий следующим трём условиям:

• в ней нет одинаковых множителей
• в каждом множителе нет повторяющихся переменных
• каждый множитель содержит все переменные, от которых зависит булева функция

(в таблице истинности берутся строки, где функция равна 0)

Отличие СДНФ и СКНФ от ДНФ и КНФ (?)
Совершенные формы (СКНФ и СДНФ) включают в себя все возможные комбинации переменных для обеспечения полноты, в то время как обычные формы (КНФ и ДНФ) могут быть неполными или избыточными.

Использование:
Каждую функцию можно представить в виде СКНФ и СДНФ, и для каждой функции существует только одна СКНФ и только одна СДНФ. СДНФ и СКНФ представляют логическую функцию в виде простой и понятной формы, что упрощает анализ и понимание ее свойств и поведения. Формы легко построить из таблицы истинности и можно использовать для реализации логических схем.

7. Определение логической функции от двух переменных. Построение таблиц истинности для всех логических функций от двух переменных. Опишите основные логические операции данной таблицы.

8. Какие есть методы минимизации логических выражений? Минимизация логических функций с использованием карты Карно. Алгоритм построения карты Карно и ее использование для минимизации логических функций.

Методы минимизации логических выражений

• Алгебраический метод: Использует законы алгебры логики для упрощения выражений.
• Метод карты Карно: Основан на графическом представлении булевых функций в виде таблицы, где соседние клетки представляют логически связанные термы.

Минимизация логических функций с использованием карты Карно
Построение карты Карно:

• Создание таблицы, в которой каждая ячейка представляет комбинацию значений переменных и соответствующее значение функции.
• Группировка термов: Объединение соседних ячеек с единицами в группы, которые представляют логически связанные термы.
• Построение минимизированного выражения: Использование групп для записи минимизированного выражения, где каждая группа представляет один терм.

Алгоритм построение карты Карно и её использования для минимизации:

9. Какие основные логические элементы вы знаете? Постройте таблицу логических функций от двух переменных и обозначьте их название, и нарисуйте соответствующий логический вентиль.

10.Что такое таблица истинности и как ее использовать для описания работы логического элемента? Что такое логический вентиль и как он работает? Какие типы логических вентилей вы знаете?

Таблица истинности — это таблица, которая показывает, как логический элемент (или функция) ведет себя для разных комбинаций входных значений, указывая соответствующие выходные результаты.

Логический вентиль — это электронное устройство, которое принимает логические сигналы на входе, выполняет операцию (например, И, ИЛИ, НЕ) и выдает соответствующий результат на выходе.

Типы логических вентилей:

• И (AND): возвращает 1, только если оба входа равны 1.
• ИЛИ (OR): возвращает 1, если хотя бы один из входов равен 1.
• НЕ (NOT): инвертирует входной сигнал (меняет 1 на 0 и наоборот).
• Исключающее ИЛИ (XOR): возвращает 1, если количество входов, равных 1, нечетно.
• И-НЕ (NAND): Инвертированная версия И - возвращает 0 только в случае, если оба входа равны 1.
• ИЛИ-НЕ (NOR): Инвертированная версия ИЛИ - возвращает 0, если хотя бы один из входов равен 1.

11.Что такое комбинационная логика и как она работает? В чем отличие комбинационной логики от последовательной? Приведите примеры комбинационной логики и последовательной

Комбинационная логика:

• Определение: выходы зависят только от текущих входов, без состояния и обратной связи.
• Принцип работы: мгновенно реагирует на входы, без памяти.
• Примеры: дешифраторы, мультиплексоры.

Последовательная логика:

• Определение: выходы зависят от текущих входов и предыдущего состояния.
• Принцип работы: включает элементы с памятью (триггеры, регистры).
• Примеры: триггеры, регистры, счетчики.

Отличие от последовательной логики

12.Что такое логический базис функции? Какие базисы существуют? Как преобразовать логическую схему из одного базиса в другую?

Логический базис функции — минимальный набор логических функций для построения любых других функций.

Типы базисов:

• {И, ИЛИ, НЕ} (не является минимальным, избыточный базис)
• Из двух функций: {НЕ, ИЛИ}, {НЕ, И}
• Из одной функции: {НЕ-ИЛИ (стрелка Пирса)}, {НЕ-И (штрих Шеффера)}

Преобразование между базисами:
Используя законы алгебры логики, можно перейти от одного базиса к другому. Например, из базиса {И, ИЛИ, НЕ} можно перейти к базису {НЕ-И} или {НЕ-ИЛИ} с помощью двойного отрицания и законов де Моргана.

13. Дайте определение алгебры логики (булевой алгебры). Перечислите основные законы алгебры логики. Как можно использовать законы алгебры логики для минимизации логических схем?

Логические схемы представляют в виде логических функции, чтобы, используя законы алгебры логики, сократить функцию и затем составить новую более простую схему.

14.Сформулируйте закон двойного отрицания. Сформулируйте законы коммутативности и ассоциативности для логического “И” и “ИЛИ”. Сформулируйте законы дистрибутивности. Сформулируйте правила де Моргана. Сформулируйте правило поглощения.

15.Что такое функциональное устройство? Какие функции оно может выполнять? Что такое комбинационная логика? Какие этапы создания комбинационного функционального устройства существуют?

Функциональное устройство — это система, выполняющая определенные функции по заданным правилам.

Функции функционального устройства:

• Обработка данных: Выполнение операций над входными данными.
• Генерация сигналов: Создание выходных сигналов из входных данных.
• Принятие решений: Определение последовательности действий на основе входных условий.

Комбинационная логика — часть цифровой логики, где выход зависит только от текущих входов без состояния.

Этапы создания:

• Выбор базиса.
• Представление функции в виде таблицы истинности или совершенно нормальной формы.
• Минимизация функции.
• Перевод функции в базис, в котором будет строиться схема.
• Составление схемы на элементах базиса.

16.Что такое минимизация функции? Какие методы минимизации функций существуют? Что такое карта Карно? Для чего она нужна? Как она составляется? Приведите пример составления карты Карно по таблице истинности?

Минимизация функции — это процесс упрощения логической функции с сохранением её функциональности.

Методы минимизации функций:

• Алгебраический метод: использует законы алгебры логики для упрощения выражений.
• Метод карты Карно: основан на графическом представлении булевых функций в виде таблицы, где соседние клетки представляют логически связанные термы.

Карта Карно используется для:

• Минимизации логических функций: облегчает создание минимального логического выражения.
• Оптимизации логических схем: помогает разрабатывать более компактные и эффективные цифровые устройства.
• Анализа и синтеза комбинационных схем: позволяет лучше понять взаимосвязи входных и выходных переменных в цифровых устройствах.

Составление карты Карно

17.Что такое СДНФ и СКНФ чем они отличаются от ДНФ и КНФ? Как формируются СДНФ и СКНФ по таблице истинности? Как составляются ДНФ и КНФ? Что значит привести к базису И-НЕ, ИЛИ-НЕ? Что такое стрелка Пирса и штрих Шеффера?

СДНФ (совершенная дизъюнктивная нормальная форма) — частный случай ДНФ, удовлетворяющий следующим трём условиям:

• в ней нет одинаковых слагаемых
• в каждом слагаемом нет повторяющихся переменных
• каждое слагаемое содержит все переменные, от которых зависит булева функция

СКНФ (совершенная конъюнктивная нормальная форма) — частный случай КНФ, удовлетворяющий следующим трём условиям:

• в ней нет одинаковых множителей
• в каждом множителе нет повторяющихся переменных
• каждый множитель содержит все переменные, от которых зависит булева функция

Отличие СДНФ и СКНФ от ДНФ и КНФ (?)
Совершенные формы (СКНФ и СДНФ) включают в себя все возможные комбинации переменных для обеспечения полноты, в то время как обычные формы (КНФ и ДНФ) могут быть неполными или избыточными.

Формирование СДНФ и СКНФ:

• СДНФ: составляется, группируя строки таблицы истинности с единицами.
• СКНФ: составляется, группируя столбцы таблицы истинности с нулями.

Формирование ДНФ и КНФ:
Форма СДНФ или СКНФ минимизируется алгебраическим методом или методом карт Карно.

Привести к базису И-НЕ, ИЛИ-НЕ:
Это означает, что любая логическая функция может быть представлена с использованием только операций И-НЕ (стрелка Пирса) или ИЛИ-НЕ (штрих Шеффера).

Аппаратное обеспечение вычислительной техники

1. Что такое логический вентиль? Как создать логический вентиль из аппаратных средств? Приведите пример.

Логический вентиль — это базовый элемент цифровой электроники, выполняющий логическую операцию.

Пример — логический вентиль "И".
Для формирования элемента "И" было необходимо использовать четыре транзистора, которые были объединены попарно в последовательную связь: два транзистора типа P (с кружочком) и два транзистора типа N, соединенных с землей и питанием соответственно.

2. Что такое КМОП логика? В чем ее особенность? Соберите логические вентили (И, ИЛИ, НЕ, ИЛИ-НЕ, И-НЕ) на КМОП логике.

КМОП логика (Комплементарная металл-оксид-полупроводник) представляет собой технологию изготовления интегральных схем, с помощью комплементарных транзисторов (N-канальных и P-канальных)

Особенности КМОП логики:

• Комплементарность (элементы дополняют друг друга)
• Низкое энергопотребление
• Высокая скорость работы

Логические вентили (И, ИЛИ, НЕ, ИЛИ-НЕ, И-НЕ)

3. Какие типы транзисторов существуют? В чем их разница и особенности? Принцип работы МОП-транзистора p-типа и n-типа? Что означает p-тип и n-тип транзистора?

Типы транзисторов:

• P-тип: Заряд положительный, ток протекает при отрицательном напряжении на воротах.
• N-тип: Заряд отрицательный, ток протекает при положительном напряжении на воротах.

Принцип работы:

• P-тип транзистор: Протекание тока от истока к стоку при отрицательном напряжении на воротах.
• N-тип транзистор: Протекание тока от истока к стоку при положительном напряжении на воротах.

Значение:

• n-типа — носителями зарядов являются электроны.
• p-типа — носители зарядов – положительно заряженные «дырки».

4. Что такое реле? Принцип работы реле? В чем сходства и различия между реле и транзистором? Как собираются логические вентили (И, ИЛИ, НЕ, ИЛИ-НЕ, И-НЕ) на реле?

Реле — это устройство, которое управляет электрическими сигналами с помощью магнитного поля, создаваемого электромагнитной катушкой.

Принцип работы: Контакты реле переключаются под воздействием этого поля, открывая или закрывая электрические цепи.

Сходства с транзистором: Используются для управления сигналами.

Различия:

• Реле - электромеханическое, транзистор - полупроводниковое устройство.
• Реле для высоких токов, транзисторы для малых токов.
• Транзисторы компактнее и быстрее.

Логические вентили на реле могут быть собраны следующим образом:

• Логическое И (AND): подключите два реле последовательно.
• Логическое ИЛИ (OR): подключите два реле параллельно.
• Логическое НЕ (NOT): Используйте одно реле и подключите его так, чтобы активация реле приводила к разрыву цепи.
• Логическое ИЛИ-НЕ (NOR): сначала создайте логическое ИЛИ, затем добавьте реле для инверсии сигнала/ подключите два нормально замкнутых реле последовательно.
• Логическое И-НЕ (NAND): сначала создайте логическое И, затем добавьте реле для инверсии сигнала/ подключите два нормально замкнутых реле параллельно.
  

5. Что такое электронные компоненты? Какие основные электронные компоненты вы знаете? Где и как они применяются? Что такое интегральная схема?

Электронные компоненты — это базовые элементы, из которых строятся электронные системы. Они выполняют различные функции, такие как усиление сигналов, фильтрация, коммутация и хранение данных в электрических цепях.

Основные электронные компоненты:

• Резисторы: ограничивают ток. Везде, где нужно управлять электрическим током.
• Конденсаторы: хранят и высвобождают электрическую энергию, фильтруют сигналы. Применяются в блоках питания, фильтрах и других устройствах.
• Катушки индуктивности: создают магнитное поле при прохождении тока, используются в фильтрах и индуктивных устройствах.
• Диоды: передают ток только в одном направлении. Используются в выпрямителях, светодиодах.
• Транзисторы: управляют током и напряжением, используются для усиления сигналов, создания логических элементов.
• Операционные усилители: усиливают сигналы в электрических цепях.
• Микросхемы (Интегральные схемы): являются элементной базой всех современных радиоэлектронных устройств, устройств вычислительной техники, информационных и телекоммуникационных систем.
• Реле — это устройство, которое управляет электрическими сигналами с помощью магнитного поля, создаваемого электромагнитной катушкой. Может применяться для различных функций, таких как защита, управление и автоматизация в различных устройствах.

Интегральная схема — функционально законченное микроэлектронное изделие, представляющее собой совокупность электрически связанных между собой элементов (транзисторов и др.), сформированных в полупроводниковой монокристаллической пластине.

6. Что такое сигнал? Какие виды физических сигналов вы знаете? В чем разница между аналоговым, дискретным и цифровым сигналом? Что такое дискретизация сигнала? Что означает период дискретизации сигнала? Что такое квантование сигнала? Как период дискретизации и квантования сигнала связан с точностью сигнала?

Сигнал — это физическая величина, представляющая изменение во времени, передаваемое через электрические, звуковые или оптические системы.

Виды сигналов:

• Электрические (носитель информации - изменяющиеся во времени ток или напряжение в электрической цепи)
• Магнитные
• Тепловые
• Сигналы ионизирующих излучений
• Оптические/световые
• Акустические (звуковые)

Типы сигналов:

• Аналоговый: непрерывное изменение во времени. Пример - звуковая волна.
• Дискретный: прерывистый сигнал, принимающий отдельные значения в определенные моменты. Пример – код Морзе.
• Цифровой: можно представить в виде последовательности дискретных (цифровых) значений. Пример – цифровая аудиозапись.

Дискретизация сигнала — превращение аналогового сигнала в дискретный, то есть в последовательность отдельных значений.

Период дискретизации — интервал времени между отсчетами сигнала. Чем меньше период дискретизации, тем более детализированным будет представление сигнала.

Квантование сигнала — это превращение непрерывного диапазона значений амплитуды в ограниченный набор дискретных уровней.

Связь с точностью сигнала:

• Меньший период дискретизации и меньший шаг квантования: более точное представление сигнала.

7. Что такое цифровой сигнал? Как он выглядит? Что такое передний фронт сигнала? Что такое задний фронт сигнала? Что такое верхний уровень сигнала? Что такое нижний уровень сигнала? Что такое помехи и как они влияют на сигнал?

Цифровой сигнал — сигнал, который можно представить в виде последовательности дискретных (цифровых) значений.

Внешний вид: Последовательность дискретных уровней, как лестница.

Передний фронт — переход с низкого уровня к высокому.

Задний фронт — переход с высокого уровня к низкому.

Верхний уровень — высокий уровень напряжения.

Нижний уровень — низкий уровень напряжения.

Помехи — внешние воздействия, могут искажать сигнал, вызывая ошибки.

8. Опишите принцип передачи сигнала? Что такое передатчик, приемник? Что такое канал передачи, приведите примеры канала передачи? Что означает кодирование и декодирование сигнала? Что такое кодировка и язык кодировки?

Принцип передачи сигнала

• Источник: генерирует сигнал.
• Передатчик: преобразует сигнал для передачи.
• Канал передачи: среда передачи (провод, радиоволны).
• Приемник: принимает сигнал от канала и декодирует его.
• Получатель: получает сигнал.

Передатчик переводит информацию в передаваемую форму.

Приемник получает и восстанавливает информацию.

Канал передачи — среда передачи сигнала.

• Проводной: кабель, витая пара.
• Беспроводной: радиоволны, инфракрасное излучение.

Кодирование — представление информации для передачи (бинарный код, например).

Декодирование — обратное преобразование.

Кодировка — представление символов в виде битов.

Язык кодировки — набор правил для соответствия символов и их кодов
(например, UTF-8).

Компьютерная арифметика

1. Какие простейшие арифметические и логические операции возможно выполнять при использовании логических вентилей? Перечислите эти операции и опишите принцип их выполнения. (?)

Простейшие арифметические операции с использованием логических вентилей:

• Логическое сложение (ИЛИ). Принцип: если хотя бы один из входов равен 1, то на выходе будет 1.
• Логическое умножение (И). Принцип: если оба входа равны 1, то на выходе будет 1.
• Логическое отрицание (НЕ). Принцип: инвертирует входной сигнал.

Простейшие логические операции с использованием логических вентилей:

• Логическое отрицание конъюнкции (NAND). Принцип: равно 0 только в том случае, если оба входа равны 1.
• Логическое отрицание дизъюнкции (NOR). Принцип: равно 1 только в том случае, если оба входа равны 0.

2. Опишите принцип устройства полусумматора, полного однобитного сумматора и 4х битного сумматора. Какие максимальные числа может складывать 8ми битный сумматор? 16ти битный сумматор?

Полусумматор
Принцип: XOR для суммы, AND для переноса.

Полный однобитный сумматор:
Принцип: принимает два бита и входной перенос, выдает сумму (сумма суммы входов и входного переноса) и выходной перенос (перенос суммы входов и входного переноса OR выходной перенос суммы входов).

4-битный сумматор:
Принцип: состоит из четырех однобитных сумматоров (каждый принимает по биту от двух чисел), где каждый следующий принимает выходной перенос предыдущего в качестве входного переноса. Макс число 2⁴-1=15

8-битный сумматор:
Максимальное число: 2⁸-1=255 (-1, потому что мы считаем ещё число 0)

16-битный сумматор:
Максимальное число: 2¹⁶-1=65535

3. Как происходит вычитание двух чисел? Какие способы представления отрицательных чисел существует? Опишите эти способы? В чем разница между знаковым и беззнаковым представлением отрицательный двоичных чисел?

Вычитание двух чисел происходит путем вычитания каждого разряда числа в столбик, начиная с младших разрядов или сложением чисел с использованием дополнительного кода.

Способы представления отрицательных чисел:

• Прямой код со знаковым разрядом: первый бит для знака, остальные для модуля числа.
• Обратный код: инвертируются все биты.
• Дополнительный код: инвертируются все биты и прибавляется 1.

Разница между знаковым и беззнаковым представлением отрицательных двоичных чисел

• Беззнаковое: только положительные числа, в 8 битах можно зашифровать числа от 0 до 255.
• Знаковое: положительные и отрицательные числа, в 8 битах можно зашифровать числа от -128 до 127 (дополнительный код).

4. Что такое прямой код, обратный код и дополнительный код? Как преобразовать 4х битный сумматор в 4х битный вычитатель использую дополнительный код? Постройте абстрактную схему такого устройства. Какой диапазон чисел у 8ми битного знакового числа в дополнительном коде?

Прямой код:
Обычное двоичное представление числа, в основном используется для представления неотрицательных чисел. Чтобы записывать отрицательные числа, старший разряд объявляется знаковым (0 означает, что число положительное, 1 – что число отрицательное).

Обратный код:
Инвертирование всех битов прямого кода. Положительные числа остаются без изменений, для отрицательных инвертируются все биты.

Дополнительный код:
Инвертирование всех битов прямого кода и прибавление 1. Положительные числа остаются без изменений, для отрицательных инвертируются все биты и прибавляется 1. Позволяет заменить операцию вычитания на операцию сложения.

Преобразование 4х битного сумматора в 4х битный вычитатель

Инвертор:

4-х битный вычитатель:

Диапазон 8-битного знакового числа в дополнительном коде от -128 до 127.

Комбинационная логика

1. Что такое шифратор и дешифратор. В чем их различия? Как строятся шифраторы и дешифраторы. Приведите пример шифратора и дешифратора.

Шифратор — это устройство, преобразующее входные данные в код или шифр.

Дешифратор — это устройство, восстанавливающее исходные данные из шифра.

Различия

• Шифратор: Преобразует исходные данные в шифр.
• Дешифратор: Восстанавливает исходные данные из шифра.

Шифратор

Дешифратор

2. Что такое мультиплексор и демультиплексор? Опишите принцип работы мультиплексора и демультиплексора? Как мультиплексор и демультиплексор обозначаются на схемах? Где они применяются?

Мультиплексор — устройство, выбирающее один из нескольких входных сигналов для передачи на выход. Принцип работы: Выбор сигнала зависит от управляющих входов.
Обозначается трапецией, "MUX".

Демультиплексор — устройство, направляющее входной сигнал на один из нескольких выходов. Принцип работы: Распределение сигнала основывается на управляющих входах. Обознчачается трапецией, "DEMUX".

Применение

• Мультиплексоры: Используются для выбора входных сигналов, коммутации, передачи данных. (какое число из памяти показать)
• Демультиплексоры: Применяются в декоммутации, управлении данными по различным каналам. (в какую ячейку памяти записать число)

Последовательная логика

1. В чем отличие последовательной логики от комбинационной? Приведите примеры устройств с последовательной логикой? Что такое тактовый генератор? В чем разница между синхронным и асинхронным?

Комбинационная логика: Состояние выхода зависит только от текущих входов, предыстория не учитывается.

Последовательная логика: Предыдущее состояние влияет на последующие, обеспечивая память. (триггеры, счётчики, регистры)

Тактовый генератор — устройство, генерирующее такты процессора. Определяет "частоту" работы процессора.

Синхронная работа: устройства синхронизируются общим тактовым импульсом.

Асинхронная работа: устройства работают независимо от тактовых импульсов.

2. Что такое триггер? Какие виды триггеров существует? Опишите принцип работы основных триггеров. В чем разница между синхронной и асинхронной работой триггеров?

Триггер – базовое последовательностное устройство, переходящее между двумя состояниями под воздействием входных сигналов; мельчайший элемент памяти. Он играет ключевую роль в последовательностных логических устройствах.

Виды триггеров и принцип работы

• RS-триггер: R=1 -> установить 0, S=1 -> установить 1.
• D-триггер: записывает значение D по входу CLK.
• Т-триггер: изменяет записанное значение на противоположное при установлении 1 на T.
• ТС-триггер: изменяет значение на противоположное по входу C при T=1.
• JK-триггер: J=1, K=0 -> установить 1; J=0, K=1 -> установить 0, J=K=1 -> инвертировать значение. Работает по входу CLK.

Асинхронные триггеры меняют состояние непосредственно при появлении информационного сигнала.

Синхронные триггеры реагируют на информационные сигналы только при наличии сигнала на входе синхронизации (тактовом входе).

3. RS-триггер, его структура и принцип работы. RS-триггер работающий синхронно и асинхронно в чем разница? Нарисуйте схемы синхронного и асинхронного RS-триггера. Напишите таблицу перехода синхронного и асинхронного RS-триггера. Приведите пример устройства, использующего RS-триггер

RS-триггер сохраняет предыдущее состояние при нулевых входах и меняет его при подаче единицы.

Структура RS-триггера: RS-триггер состоит из двух инверторов и двух NAND-вентилей (иногда используются NOR-вентили). Входы S (Set) и R (Reset) контролируют установку и сброс триггера соответственно.

Принцип работы:

• Подача единицы на вход S переводит в состояние "1".
• Подача единицы на вход R переводит в состояние "0".
• Запрещенное состояние: Два входа, находящиеся в состоянии "1", приводят к потере свойства триггера, ибо переключение сигналов 1 на информационные входы вызовет появление логических нулей на выходах.

Асинхронный режим:
Изменение состояния может происходить независимо от тактового сигнала.

Синхронный режим:
Изменение состояния происходит только при С=1

Таблица переходов:

Применение RS-триггера: RS-триггеры используются в цифровых схемах для создания памяти и регистров, а также в устройствах, где необходимо управлять последовательностью сигналов.

4. Дать определение D-триггеру. Какие режимы работы D-триггера существуют? Что такое предустановка и сброс D-триггера? Напишите таблицы переходов D-триггера, работающего по верхнему уровню, работающего по переднему фронту.

D-триггер – это синхронный триггер с одним информационным входом предназначенным для задержки логического сигнала.

Режимы работы:

• По верхнему уровню (запись, когда С=1)
• По нижнему уровню (запись, когда С=0)
• По переднему фронту (запись, во время перехода с 0 на 1)
• По заднему фронту (запись, во время перехода с 1 на 0)

Предустановка (Preset): Устанавливает Q в 1.
Сброс (Clear): Устанавливает Q в 0.

Таблицы переходов

5. Построить D-триггер, работающий по верхнему уровню из RS-триггеров. Построить D-триггер, работающий по переднему фронта с предустановкой и сбросом. Приведите примеры применения D-триггеров.

Примеры применения D-триггеров

• Регистры
• Счётчики
• Делители частоты
• Сумматоры с памятью

6. Дать определение T-триггера. Какие режимы работы есть у T-триггера? Напишите таблицу переходов T-триггера. Построить T-триггер из D-триггеров, работающих по переднему фронту.

T-триггер

• Асинхронный: устройство, которое меняет свое состояние при каждом тактовом импульсе (один вход).
• Синхронный (или ТС-триггер): устройство, которое меняет свое состояние при каждом тактовом импульсе в зависимости от сигнала T (два входа).

Применяется, например, для деления частоты.

Режимы работы:

• по переднему фронту
• по заднему фронту

Таблица переходов (по переднему фронту):

T-триггер из D-триггера

7. Дайте определение регистру. Какого его назначение и где он применяется? Приведите примеры. Построить регистр из триггеров. Опишите принцип работы регистра.

Регистр — это устройство для временного хранения и обработки данных в цифровых системах.

Примеры использования: в процессорах, счетчиках, устройствах ввода-вывода.

Регистр из триггеров (синхронный)

8. Дайте определение счетчику. Какого его назначение и где он применяется. Постройте счётчик из триггеров. Опишите принцип работы счетчиков. Какие режимы работы счетчиков вы знаете?

Счетчик — это устройство, предназначенное для подсчета и отображения количества сигналов или событий в цифровых системах.
Он применяется для измерения и контроля количественных параметров в различных областях, таких как электроника, автоматика, телекоммуникации и другие.

Счетчики классифицируются по характеру счета на суммирующие, вычитающие и реверсивные. Суммирующие прибавляют импульсы, вычитающие вычитают, а реверсивные могут как прибавлять, так и вычитать импульсы. По согласованности переключения триггеров в их составе существуют асинхронные и синхронные счетчики.

9. Что такое тактовый генератор? Для чего он применяется? Что такое делитель частоты? Как построить делитель частоты из D-триггеров?

Тактовый генератор — устройство для создания регулярных сигналов, используемых для синхронизации.
Он применяется для управления временными процессами в цифровых системах.

Делитель частоты — устройство для уменьшения частоты тактового сигнала. Можно построить из D-триггеров, соединяя их последовательно.

10.Что такое память? В чем она измеряется? Постройте память 4x4 RAM на регистрах.

Память — это устройство, способное сохранять, хранить и восстанавливать данные. Измеряется в битах, байтах, килобайтах и т.д.

4x4 RAM — оперативная память (Random Access Memory – память с произвольным доступом) с четырьмя регистрами по 4 бита.

(поменять стандартные регистры на 4-х битные)

11.Построить сумматор с памятью и сумматор с аккумулятором. Какие триггеры использовались при построение данного устройства? Почему?

Сумматор с памятью

Сумматор с аккумулятором

Используются триггеры по фронту, так как при использовании триггеров по уровню при сложении с числом из регистра, если оставить запись числа = 1, регистр будет беспрерывно записывать новую сумму, увеличивающуюся из-за постоянного обновления числа в регистре.

Теория информации

1. Дайте определение науки информатика? Дайте определение термину информация? В каких единицах происходит измерение информации? Напишите формулу Хартли с пояснениями и примерами.

Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий.

Информация – сведения об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые уменьшают имеющуюся о них степень неопределенности, неполноты знаний.

Единицы измерения информации: биты, байты, килобайты и т.д.

Формула Хартли

Где N — количество символов в используемом алфавите (мощность алфавита), K — длина сообщения (количество символов в сообщении), I — количество информации в сообщении в битах.
Пример: восьмеричная система счисления -> N=8, сообщение “145” -> K=3, тогда I=9 бит.

2. Дайте определение следующим терминам: канал связи, сигнал, помехи, алфавит, код, язык, сообщение, данные. Приведите пример системы по передачи данных.

Канал связи — среда передачи сигналов между устройствами.
Сигнал — материальное воплощение сообщения для использования при передаче, переработке и хранении информации.
Помехи — нежелательные искажения или вмешательства в сигнал.
Алфавит — набор символов для представления данных.
Код — система условных знаков, применяемых для передачи, обработки, хранения информации.
Язык — множество конечных слов (строк, цепочек) над конечным алфавитом.
Сообщение — передаваемая информация.
Данные — факты, числа, текст и т.д., обрабатываемые устройствами.

Пример системы передачи данных:
Компьютер передает текстовое сообщение принтеру через кабель, где возможны помехи. Принтер получает сигнал, декодирует его и выводит текст на бумаге.

3. Что такое информационная энтропия? В чем смысл информационной энтропии? Напишите формулу информационной энтропии Шеннона. Приведите пример вычисления информационной энтропии по формуле Шеннона.

Информационная энтропия — мера неопределённости, хаотичности информации.
Смысл: чем выше энтропия, тем больше неопределённости в сообщении и тем больше бит информации требуется для его передачи.

Формула информационной энтропии Шеннона
, где p_i – вероятность появления события i.

Пример:
Красный сигнал появляется с вероятностью 0,25, а зелёный – с вероятностью 0,75. Информационная энтропия сообщения
Если бы сигналы появлялись равновероятно, то
бит

Теория автоматов

1. Введение в теорию автоматов: основные определения и понятия. Что такое автомат и какие типы автоматов существуют? Сформулируйте абстрактный автомат.

Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.

Автомат:

• В общем: самостоятельно действующее по заданной программе устройство.
• Абстрактный автомат — модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных.

Типы автоматов:

• Конечный автомат (число возможных внутренних состояний конечно)
• Детерменированный конечный автомат (следующее состояние однозначно определяется текущим состоянием и входным символом)
• Недетерминированный конечный автомат (следующее состояние в общем случае не определено)
• Вероятностный конечный автомат (переход в последующие состояния происходит с некоторыми вероятностями)

2. Сформулируйте конечный детерминированный автомат с пояснениями. Какие существуют способы задания конечного автомата? Приведите пример. (?)

Конечный детерминированный автомат (ДКА) — математическая модель с ограниченным числом состояний, где переходы определены символами алфавита, и есть начальное и конечные состояния.

Способы задания конечного автомата

• Табличный (матрицы переходов и выходов)
• Графический (с помощью графов)
• Аналитический (с помощью формул)

3. Что такое синтез автомата? Что представляет собой граф переходов автомата? Что такое таблица переходов автомата? Приведите пример конечного автомата. (?)

Синтез автомата — это процесс создание автомата на основе заданных условий.

Граф переходов представляет собой графическое изображение состояний и переходов между ними с учетом символов алфавита.

Таблица переходов — это структурированная форма, автомата где пересекаются состояния и символы, указывая соответствующие переходы.

Пример

4. Детерминированные и недетерминированные конечные автоматы: определение и основные характеристики. В чем разница между детерминированными и недетерминированными конечными автоматами? Как определить, является ли конечный автомат детерминированным или недетерминированным? Каковы основные характеристики детерминированных и недетерминированных конечных автоматов?

Детерминированный конечный автомат (ДКА) — автомат, где для каждой пары состояние-входной символ существует единственный переход. Полностью определен и предсказуем.

Недетерминированный конечный автомат (НКА) — автомат, где для некоторых пар состояние-входной символ существует более одного возможного перехода. Допускает неоднозначность и более сложное поведение.

Определение типа автомата

• ДКА: Для каждой пары состояние-входной символ существует единственный переход.
• НКА: Для некоторых пар состояние-входной символ существует более одного возможного перехода.

5. Автоматы Мили и Мура: определение, особенности и взаимосвязь. Дайте формальное определение автоматам Мили и автоматам Мура. В чем состоят особенности каждого из этих типов автоматов? (?)

Автомат Мили

• Выход зависит от текущего состояния и входного символа.
• Выход меняется сразу после изменения входа.

Автомат Мура

• Выход зависит только от текущего состояния.
• Выход меняется при переходе между состояниями.

Взаимосвязь
Оба типа автоматов представляют собой конечные автоматы.
Различие в том, как изменяются выходные сигналы: при изменении входа (Мили) или при переходе между состояниями (Мура).

Формальные определения

Автомат Мили

• Состояния: S
• Входной алфавит: X
• Выходной алфавит: Y
• Переходы: δ: S × X → S
• Выходы: λ: S × X → Y
• Начальное состояние: s₀∈S

Автомат Мура

• Состояния: S
• Входной алфавит: X
• Выходной алфавит: Y
• Переходы: δ: S × X → S
• Выходы: λ: S → Y
• Начальное состояние: s₀∈S

Схемы

1) Схема логических вентилей на КМОП логике (И, ИЛИ, НЕ, ИЛИ-НЕ, И-НЕ)

2) Построить схему мультиплексора с двумя управляющими битами

3) Построить схему демультиплекссчора с двумя управляющими битами

4) Построить схему полусумматора из логических вентилей, построить схему полного однобитного сумматора из двух полусумматоров. Обозначить входы и выходы и написать, что они означают.

Полусумматор (carry – перенос)

Полный однобитный сумматор (CI – перенос из предыдущего сумматора, CO – перенос в следующий сумматор)

5) Построить вычитатель из сумматора и инвертора, используя готовый сумматор. Обозначить входы и выходы.

Инвертор

Вычитатель
(заменить стандартный сумматор на 4-х битный)

6) Построить сумматор с аккумулятором, используя готовый сумматор и готовый регистр.

Сумматор с аккумулятором

7) Построить асинхронный RS-триггер из логических вентилей.

8) Построить синхронный RS-триггер из логических вентилей

9) Построить D-триггер, работающий по уровню из логических вентилей. Обозначить входы и выходы.

По верхнему уровню

10)Построить D-триггер, работающий по фронту используя готовые D-триггеры, работающие по уровню. Обозначить входы и выходы.

По переднему фронту
(поменять стандартные D-триггеры на высокий уровень)

11)Построить T-триггер из D-триггеров, работающих по уровню. Обозначить входы и выходы.

T-триггер
(поменять стандартные D-триггеры на высокий уровень)

12)Построить 4х битный регистр из D-триггеров. Обозначить входы и выходы.

Асинхронный регистр

13)Построить счетчик из T-триггеров. Обозначить входы и выходы.

14)Построить делитель частоты из D-триггеров.

15)Построить память на 4 бита и 4 ячейки.

(поменять стандартные регистры на 4-х битные)